package com.hch.datastructure.simpledemo;

/**
 * @author HeCongHui
 * @date 2022/7/6 19:37
 */
public class BinarySearch {

    private Integer[] orderlyArray;

    private Integer high;

    private Integer low;

    public BinarySearch(Integer[] orderlyArray) {
        this.orderlyArray = orderlyArray;
        this.high = orderlyArray.length - 1;
        this.low = 0;
    }

    public Integer searchOrderlyArray(Integer item) {
        while (high <= low) {
            //向下取整
            Integer mid = (int) Math.floor((high - low) / 2);
            //检查中间元素
            Integer guess = orderlyArray[mid];
            if (guess.equals(item)) {
                return mid;
            } else if (guess > item) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return null;

    }

    public Integer recursionSearch(Integer item) {

        if (low >= high) {
            return null;
        }
        Integer mid = (int) Math.floor((high - low) / 2);
        Integer guess = orderlyArray[mid];

        //向下取整
        if (guess.equals(item)) {
            return mid;
        } else if (guess < item) {
            low = mid + 1;
            return recursionSearch(item);
        } else {
            high = mid - 1;
            return recursionSearch(item);
        }

    }
}
